//==================================================================
//  Copyright (C) 2006  Davide Pasca
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//==================================================================
//==
//==
//==
//==================================================================

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "psys.h"
#include "m6d_tvert.h"
#include "m6d_mesh.h"

//==================================================================
using namespace M6D;

#ifdef _DEBUG
//#define PARANOIA
#endif

//==================================================================
static const int	MAX_TRI_PER_VERT			= 128;
static const float	MAXIMUM_STRENGTH			= 10e20f;
static const float	MAX_ANGLE_BETWEEN_NORMALS	= 60;

static const float	MAX_CURV_STRE_TO_MAKE_EDGE	= (MAX_ANGLE_BETWEEN_NORMALS / 180.0f);

//==================================================================
struct VertexEdgeInfo
{
	float	edge_strength;
	int		edge_vert;
	float	inherited_edge_strength;
};

//==================================================================
static int findOtherVertexInEdge( const Triangle &tr_a,
									  const Triangle &tr_b,
									  int avoid_vertex ) throw(...)
{
	int a1 = tr_a[0];
	int b1 = tr_a[1];
	int c1 = tr_a[2];
	int a2 = tr_b[0];
	int b2 = tr_b[1];
	int c2 = tr_b[2];

	int a_shared = ( a1 == a2 || a1 == b2 || a1 == c2 ) ? 1 : 0;
	int b_shared = ( b1 == a2 || b1 == b2 || b1 == c2 ) ? 1 : 0;
	int c_shared = ( c1 == a2 || c1 == b2 || c1 == c2 ) ? 1 : 0;

	if ( (a_shared + b_shared + c_shared) == 2 )
	{
		if ( a_shared && a1 != avoid_vertex )
			return a1;

		if ( b_shared && b1 != avoid_vertex )
			return b1;

		if ( c_shared && c1 != avoid_vertex )
			return c1;
		
		PASSERT( 0 );	// impossible !!
	}

	// none found
	return -1;
}

//==================================================================
static PFORCEINLINE float calc_edge_strength( float curv, const PMath::Vector3 &v1, const PMath::Vector3 &v2 )
{
	return curv * (v2-v1).GetLength();
}

//==================================================================
static void compute_vertex_strength( VertexEdgeInfo *veinfop, TriIdx_VertIdx &tidx_vidx, int vidx,
									 MeshGeometry *gp )
{
	static const int MAX_EDGE_VERTS	= 256;

	int			edge_vert;
	float		strength;
	int			edge_verts[ MAX_EDGE_VERTS ];
	int			n_edge_verts;

	// list of triangles belonging to the vertex vidx
	TriList	&v_trigs = tidx_vidx[ vidx ];

	// vertices belonging to non-closed edges, must be preserved
	if ( v_trigs._flags & TriList::FLG_OPEN_EDGE )
	{
		veinfop->edge_vert = -1;
		veinfop->edge_strength = MAXIMUM_STRENGTH;
		return;
	}

	if NOT( v_trigs.len() )
	{
		veinfop->edge_vert = -1;
		veinfop->edge_strength = MAXIMUM_STRENGTH;
		return;
	}

	if PBADPATH( v_trigs.len() > MAX_TRI_PER_VERT )
		return;

	n_edge_verts = 0;
	
	// for a specific vertex, search all combinations of triangles that
	// share that vertex to see if there is an edge
	// - if an edge, it's put in a list

	// curv = 1 - (1 + tri.norm . trj.norm) / 2
	// curv is a strength coefficient that goes from 0 (planar triangles)
	// to 1 (planar but flipped)
	// 0.5 is 90 degrees
	
	const Triangles	&trigs = gp->GetTrigs();

	float max_curv_stre = 0.0f;
	for (int i=0; i < v_trigs.len(); ++i)
	{
		int tri	= v_trigs[ i ];

		const Triangle	&trig_i = trigs._list[ tri ];

		if NOT( trig_i.IsValid() )
			continue;

		const Vector3 &ni = trig_i.tplane.GetVector3();

		for (int j=i+1; j < v_trigs.len(); ++j)
		{
			int trj	= v_trigs[ j ];
	
			const Triangle	&trig_j = trigs._list[ trj ];

			if NOT( trig_j.IsValid() )
				continue;

			// paranoia check for consistency of the TriList structure (a triangle should only figure once !)
			PASSERT( tri != trj );

			// get into here only if both triangles share at least one edge
			edge_vert = findOtherVertexInEdge( trig_i, trig_j, vidx );
			if ( edge_vert >= 0 )
			{
				PASSERT( n_edge_verts < MAX_EDGE_VERTS );
				if ( n_edge_verts < MAX_EDGE_VERTS )
					edge_verts[ n_edge_verts++ ] = edge_vert;

				const Vector3 &nj = trig_j.tplane.GetVector3();

				float	curv_stre = 1 - (1 + ni.GetDot( nj )) * 0.5f;

				if ( curv_stre > max_curv_stre )
					max_curv_stre = curv_stre;
			}
		}
	}

	gp->GetVerts().LockR( __FILE__, __LINE__ );

	//--------------------------------- COMPUTE EDGE COST
	veinfop->edge_vert = -1;
	veinfop->edge_strength = MAXIMUM_STRENGTH;

	//max_curv_stre = MAX_CURV_STRE_TO_MAKE_EDGE/2;

	if ( max_curv_stre < MAX_CURV_STRE_TO_MAKE_EDGE )
	{
		const MultiVerts	&verts = ((const MeshGeometry *)gp)->GetVerts();
		const Vector3		*posp = verts.GetPosR();

		for (int i=0; i < n_edge_verts; ++i)
		{
#ifdef PARANOIA
			PASSERT( edge_verts[i] >= 0 && edge_verts[i] < verts.GetPosN() );
			PASSERT( vidx >= 0 && vidx < verts.GetPosN() );
#endif
			strength =
				calc_edge_strength( max_curv_stre,
									posp[ edge_verts[i] ],
									posp[ vidx        ] );

			if ( strength < veinfop->edge_strength )
			{
				veinfop->edge_strength = strength;
				veinfop->edge_vert = edge_verts[i];
			}
		}
	}

	gp->GetVerts().Unlock();
}

//==================================================================
static void recalc_neighbor_strengths( VertexEdgeInfo *veinfop, TriIdx_VertIdx &tidx_vidx, int vidx, MeshGeometry *gp )
{
	const TriList	&trilist = tidx_vidx[ vidx ];
	
	int	nt = tidx_vidx[ vidx ].len();
	
	for (int i=0; i < nt; ++i)
	{
		const Triangle &tri = gp->GetTriangle( trilist[ i ] );

		int	a = tri.pos[0];
		int	b = tri.pos[1];
		int	c = tri.pos[2];

		PASSERT( a >= 0 && b >= 0 && c >= 0 );

#ifdef PARANOIA
		u_int	n = gp->GetTrigs()._list.size();
		PASSERT( a < n &&
			     b < n &&
				 c < n );
#endif

		compute_vertex_strength( &veinfop[ a ], tidx_vidx, a, gp );
		compute_vertex_strength( &veinfop[ b ], tidx_vidx, b, gp );
		compute_vertex_strength( &veinfop[ c ], tidx_vidx, c, gp );
	}
}

//==================================================================
struct MinStack
{
	static const int	MAX_CNT = 16;

	int					_min_idx[MAX_CNT];
	float				_min_val[MAX_CNT];

	void Reset()
	{
		// make the compare valid for the the first InsertVal !
		for (int i=0; i < MAX_CNT; ++i)
		{
			_min_idx[i] = -1;
			_min_val[i] = MAXIMUM_STRENGTH;
		}
	}

	void InsertVal( int idx, float val )
	{
		if ( val < _min_val[MAX_CNT-1] )
		{
			//if ( val == 0 )
			//	val = 0;

			// scan the current val-sorted array to find where val belongs
			float	left_val = -1;
			float	right_val;

			for (int i=0; i < MAX_CNT-1; ++i)
			{
				right_val = _min_val[i];

				if ( left_val < val && val <= right_val )
				{
					// shift all down by one
					for (int j=MAX_CNT-2; j >= i; --j)
					{
						_min_idx[j+1] = _min_idx[j];
						_min_val[j+1] = _min_val[j];
					}
					// insert one above the previous [i] location
					_min_idx[i] = idx;
					_min_val[i] = val;
					return;
				}

				left_val = right_val;
			}

			// if it gets here, then it means that it's a new max value
			_min_idx[MAX_CNT-1] = idx;
			_min_val[MAX_CNT-1] = val;
		}
	}

	bool IsItemValid( int idx ) const
	{
		return _min_idx[ idx ] != -1;
	}

	int CountValidItems() const
	{
		int	cnt = 0;
		for (int i=0; i < MAX_CNT; ++i)
		{
			cnt += IsItemValid( i ) ? 1 : 0;
		}
		
		return cnt;
	}
};

//==================================================================
void Mesh::DoSimplify( TriIdx_VertIdx &tidx_vidx,
					   VertexEdgeInfo *veinfop,
					   float out_tri_ratio )
{
	_geomp->GetVerts().LockRW( __FILE__, __LINE__ );

	int nv = _geomp->GetVerts().GetPosN();

	// for every vertex, calculate the edge with the minimum strength
	// NOTE: $$$ should optimize this but working on edges directly and
	// avoid to do double the work !!
	for (int i=0; i < nv; ++i)
	{
		compute_vertex_strength( &veinfop[i], tidx_vidx, i, _geomp );
	}

	int new_nv = nv;
	int expected_nv = (int)(nv * out_tri_ratio);
	if ( expected_nv < 8 )
		expected_nv = 8;

	MinStack	min_stack;

	while ( new_nv > expected_nv )
	{
		int	good_idx;

		min_stack.Reset();

		for (int i=0; i < nv; ++i)
		{
			// make sure the vert is valid !
			if ( tidx_vidx[i].len() > 0 )
			{
				// does the vertex belong to an edge ? (it always should 8)
				if ( veinfop[ i ].edge_vert >= 0 )
				{
					float	tot_stre = veinfop[i].edge_strength + veinfop[i].inherited_edge_strength;

					min_stack.InsertVal( i, tot_stre );
				}
			}
		}

		// nothing was inserted !
		if ( min_stack.CountValidItems() == 0 )
			break;

		for (int i=0; i < MinStack::MAX_CNT; ++i)
		{
			if NOT( min_stack.IsItemValid( i ) )
				continue;

			int		kill_idx		= min_stack._min_idx[ i ];
			float	kill_strength	= min_stack._min_val[ i ];

			PASSERT( !(tidx_vidx[kill_idx]._flags & TriList::FLG_OPEN_EDGE) );

			good_idx = veinfop[ kill_idx ].edge_vert;
			// could have been invalidated by a previous ReplaceVertex() in this loop !
			if ( good_idx >= 0 )
			{
				tidx_vidx.ReplaceVertex( good_idx, kill_idx, _geomp );

				veinfop[ good_idx ].inherited_edge_strength += kill_strength * 1;//0.5f;

				recalc_neighbor_strengths( veinfop, tidx_vidx, good_idx, _geomp );

				new_nv -= 1;
			}
		}

//		for (i=0; i < nv; ++i)
//			compute_vertex_strength( &veinfop[i], tidx_vidx, i, _geomp );

//		compute_vertex_strength( &veinfop[ min_i ], tri_listp, min_i, op );
	}

	eliminateBadTrigs();

	_geomp->GetVerts().Unlock();
}

//==================================================================
void Mesh::SimplifyGeometry( float out_triangle_count_ratio ) throw(...)
{
	CleanupGeometry();

	calcTrigsNormals();

	int	nv = _geomp->GetVerts().GetPosN();

	PASSERT( nv > 2 );

	TriIdx_VertIdx	tidx_vidx( _geomp );	// assume set to 0

	std::vector<VertexEdgeInfo> veinfo_list( nv );

	DoSimplify( tidx_vidx, &veinfo_list.front(), out_triangle_count_ratio );

	killUnusedPosVerts();
	
	nv = _geomp->GetVerts().GetPosN();
	if PBADPATH( nv < 2 )
	{
		return;
	}

	calcTrigsNormals();
	calcVertsNormals( true );
}
